package leetcode.slidwidow;

import java.util.HashSet;

public class Lc567 {


    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;
        HashSet<Character> set = new HashSet<>();
        int[] cnt = new int[26];
        int sum = s1.length();
        for (int i = 0; i < s1.length(); i++) {
            set.add(s1.charAt(i));
            cnt[s1.charAt(i) - 'a']++;
        }
        for (int i = 0, j = 0; j < s2.length(); j++) {
            char c = s2.charAt(j);
            if (set.contains(c)) { //更新cnt,sum,然后判断是否凑齐了s1的字符串
                if (cnt[c - 'a'] > 0) { //字符数量没超过
                    cnt[c - 'a']--;
                    sum--;
                    if (sum == 0) { //每次更新sum就判断sum是否等于0，即是否找齐了s1的组合
                        return true;
                    }
                } else {//字符c多了，找到上一个字符c的位置，将i指向其位置的下一位，并更新cnt,sum的值
                    while (s2.charAt(i) != c) {
                        cnt[s2.charAt(i) - 'a']++;
                        sum++;
                        i++;
                    }
                    i++;//指向字符c的下一位作为字符串的起始位置
                }
            } else { //出现了s1字符集外的字符，整个i~j的字符都没用了，将i逐位移动到下一位，知道移动到当前j的下一位
                while (i < j) {
                    cnt[s2.charAt(i) - 'a']++;
                    sum++;
                    i++;
                }
                i = j + 1;
            }
        }
        return false;
    }
}
